# OTableau : WYSIWYG LaTeX code generator for OT tableaux 
# Copyright (C) 2006 Julien Eychenne
# 
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 
# MA  02110-1301, USA.

import contrib
from util.lst import fst, snd, transpose, partition
from util.fnc import cur, flip
from operator import sub
"""
A tableau consists of an input, a fixed hierarchy of constraints, a candidate
set and the associated constraint violations. It is implemented as a matrix:

 ---------------------------------
| input | C1 | C2 | C3 | ... | Cn |
 ---------------------------------
| Cand1 |  * |    |    |     |    |
|---------------------------------
| Cand2 |    | ** |    |     |    |
|---------------------------------
| Cand3 |  * |    |    |     |  * |
|---------------------------------
| ...   |    |    |    |     |    |
|---------------------------------
| Candn |    |    | ** |     |    |
 ---------------------------------

Constraints are stored in the first row; candidates are stored in the first 
column of each row. So Tableau[0] is the constraint set, Tableau[3][0] is the
third candidate, and so on. 
"""

class Tableau:
    def __init__(self, matrix):
        """Just initialise everything to empty
        (unusable values, in fact, that indicate the type)

        This first set of values should all be synchronised. For example,
        self.input should ALWAYS equal self.tableau[0][0] and
        self.col_tuples[0][0]==self.hierarchy[0]==self.tableau[0][1]
        This knowledge might need to become executed asserts if bugs
        start appearing.
        The updating methods already contain the necessary
        calls to self.initialize() to make sure everything stays synced."""


        self.tableau = matrix # see module docstring
        self.initialize(start_from='tableau')
        ## eval stuff
        self.isEvaled = False
        # a list of winners
        self.winners = []
        # for losers, record the last fatal violation
        # for winners, record the location of last critical point
        # (the last critical point is the same for all winners)
        self.fatalViolations = []
        # for every row, track the first violation
        self.minViolations = []
    def initialize(self, start_from='tableau'):
        if start_from=='tableau':
            self.setHierarchy()
            self.setInput()
            self.setOutputs()
            self.setViolations()
            self.setColTuples() # for use in Constraint Demotion
        elif start_from=='attributes':
            self.tableau = [[self.input] + self.hierarchy] + \
             [[out]+list(row) for out,row in zip(self.outputs,self.violations)]
        else:
            raise NotImplementedError('incorrect faux enumeration value')
    def setHierarchy(self):
        if len(self.tableau) > 0:
            self.hierarchy = self.tableau[0][1:]
        else:
            self.hierarchy = ['']
    def setInput(self):
        if len(self.tableau) > 0:
            self.input = self.tableau[0][0]
        else:
            self.input = ''
    def setOutputs(self):
        if len(self.tableau) > 0:
            self.outputs = [row[0] for row in self.tableau[1:]]
        else:
            self.outputs = ['']
    def setViolations(self):
        if len(self.tableau) > 0:
            self.violations = [row[1:] for row in self.tableau[1:]]
        else:
            self.violations = [[0]]
        self.column_vlns = transpose(self.violations)
    def setColTuples(self):
        if self.column_vlns:
            self.col_tuples = zip(self.hierarchy, self.column_vlns)
        else:
            self.col_tuples = [(con,[]) for con in self.hierarchy]
    def getComparativeTuples(self):
        """A comparative tableau in col_tuple form.
        This code assumes that the first row in an unevaluated standard
        tableau is the winner."""
        return [(con,[loser-col[0] for loser in col[1:]]) \
                for con,col in self.col_tuples]
    def getAbsoluteTableau(self):
        return self
    def rearrange(self, constraints):
        "rearrange hierarchy to match given order of constraints"
        self.hierarchy = constraints
        d = dict(self.col_tuples)
        self.column_vlns = map(d.__getitem__, self.hierarchy)
        self.violations = transpose(self.column_vlns)
        self.col_tuples = zip(self.hierarchy, self.column_vlns)
        self.initialize(start_from='attributes')
    def eval(self):
        self.clearFatalViolations()
        self.setMinViolations()
        self.setWinners()
        self.setFatalViolations()
        self.isEvaled = True


    def clearFatalViolations(self):
        self.winners = None
        
    def setMinViolations(self):
        "Find minimal violation among winners"
        
        self.minViolations = []
        # a bitmask of the candidates who have not yet lost
        cands = range(len(self.violations))
        for col in self.column_vlns:
            minViolation = min([col[cand] for cand in cands])
            self.minViolations.append(minViolation)
            cands = [cand for cand in cands if col[cand]==minViolation]
        self.minViolations = self.minViolations
        
    def setWinners(self):
        """The core part of Eval. It finds the list of winners."""
        # a bitmask of the candidates who have not yet lost
        winners = range(len(self.violations))
        # Losers are removed from the winning set as EVAL goes along H.
        for minV,col in zip(self.minViolations, self.column_vlns):
            winners = [cand for cand in winners if col[cand]==minV]
        self.winners = [w+1 for w in winners]

    def setFatalViolations(self):
        # Store fatal violation for each candidate
        self.fatalViolations = [-1] * len(self.violations)
        # Every candidate can be a winner
        winners = range(len(self.violations))
        # the point of last fatal violation (updated as losers are found)
        last = 0
        # Losers are removed from the winning set as EVAL goes along H.
        # Their point of removal is recorded in self.fatalViolations
        for con,(minV,col) in enumerate(zip(self.minViolations,
                                            self.column_vlns)):
            winners, losers = partition(lambda cand:col[cand]==minV,
                                        winners)
            if losers: last = con
            for cand in losers:
                self.fatalViolations[cand] = con
        #winners don't lose;instead the last critical violation is recorded
        for winner in winners:
            self.fatalViolations[winner] = last
    def getLaTeXTableau(self):
        """Produce a version of the tableau appropriate for graphical
        display.
        NOTE: Winner is not marked--this is done by other methods."""
        g = [[self.input] + self.hierarchy]
        if self.isEvaled and self.winners:
            for out,row,fatalViolation in zip(self.outputs,
                                              self.violations,
                                              self.fatalViolations):
                r = [out]
                for col,(violation,minV) in \
                        enumerate(zip(row, self.minViolations)):
                    if col==fatalViolation:
                        r.append(fatalViolationAsString(minV, violation))
                    else:
                        r.append("*"*violation)
                g.append(r)
            return g
        else:
            return g + [[o]+map(lambda violation:"*"*violation, row) \
                        for o,row in zip(self.outputs, self.violations)]
    def update(self, matrix):
        "update self.tableau based on input from the view"
        self.input = matrix[0][0].replace(u'\u261e  ','')
        self.hierarchy = [s.replace(u'\u261e  ','') for s in matrix[0][1:]]
        self.outputs = [row[0].replace(u'\u261e  ','') for row in matrix[1:]]
        self.violations = [map(star2num, row[1:]) for row in matrix[1:]]
        self.column_vlns = transpose(self.violations)
        self.setColTuples()
        self.initialize(start_from='attributes')
        
        
    def addConstraint(self):
        self.tableau[0].append('')
        for row in range(1,len(self.tableau)):
            self.tableau[row].append(0)
        self.initialize()


    def removeConstraint(self, con):
        for row in self.tableau:
            row.pop(con)
        self.initialize()

        
    def demoteConstraint(self, con):
        self.clearFatalViolations()

        if con > 0 and con < len(self.hierarchy):
            upper, newUpper = 0, 0

            for row in range(len(self.tableau)):
                upper    = self.tableau[row][con]
                newUpper = self.tableau[row][con+1]

                self.tableau[row][con]   = newUpper
                self.tableau[row][con+1] = upper

        self.initialize()


    def addCandidate(self):
        self.tableau.append([''] + [0] * (len(self.tableau[0])-1))
        self.initialize()


    def removeCandidate(self, cand):
        self.tableau.pop(cand)
        self.initialize()

        
    def demoteCandidate(self, cand):
        if cand > 0 and cand < (len(self.tableau) - 1):
            upper    = self.tableau[cand]
            newUpper = self.tableau[cand+1]

            self.tableau[cand]   = newUpper
            self.tableau[cand+1] = upper

        self.initialize()


    def factorialTypology(self):
        self.winningNames = {}
        typology = {}
        
        self.setMinViolations()
        self.setRankingsByConstraintIndex()
        self.numberOfRankings = len(self.rankings)
        
        for ranking in self.rankings:
            newTableau  = self.getNewTableau(ranking)
            newGrammar = Tableau(newTableau)
            newGrammar.setMinViolations()
            newGrammar.setWinners()
    
            winnerNames = []
            for w in range(len(newGrammar.winners)):
                winnerNames.append(self.tableau[ newGrammar.winners[w] ][0])
                self.winningNames[self.tableau[ newGrammar.winners[w] ][0] ] = 1

            winner = '] ~ ['.join(winnerNames)
            
            if not typology.has_key(winner):
                typology[winner] = []
            
            typology[winner].append(newGrammar.hierarchy)
        
        self.typology = typology
        
        # free some memory
        self.rankings = []
        
        
    def getFactorialTypologyAsString(self, includeRankings=True):
        text = ['%d rankings have been computed\n' % self.numberOfRankings]
        
        text.append( '%d winner set(s) have been found\n' % 
            len(self.typology.keys()) )
        
        for i in range(1, len(self.tableau)):
            if not self.winningNames.has_key(self.tableau[i][0]):
                text.append('No ranking gives [%s] as a winner\n' % self.tableau[i][0])
        
        text.append('\n')
        
        for winner in self.typology.keys():
            text.append( '%d ranking(s) give [%s] as winner(s):\n' % 
            (len(self.typology[winner]), winner) )
            
            for pair in self.getCommonDominations(winner):
                text.append('- common domination: %s\n' % pair)
            
            if includeRankings:
                for ranking in self.typology[winner]:
                    text.append('\t' + ' >> '.join(ranking) + '\n')
            
            text.append('\n')
        
        return ''.join(text)
        
        
    def getNewTableau(self, ranking):
        tableau = []
        
        for cand in range(len(self.tableau)):
            tableau.append([ self.tableau[cand][0] ]) # candidate
            
            for i in ranking:
                tableau[cand].append(self.tableau[cand][i])
        
        return tableau
        
        
    def setRankingsByConstraintIndex(self):
        indices = range(1, len(self.tableau))
        
        self.rankings = contrib.permutate(indices)
        
        
    def getCommonDominations(self, winner):
        """Find crucial dominations in a set of rankings based on transitivity of domination"""
        pairSet = []

        first = True

        for ranking in self.typology[winner]:
            # transitivity
            pairs = self.getPairsInRanking(ranking)
    
            if first:
                first = False
                pairSet = pairs
                continue
                
            buffer = []
            
            for pair in pairs:
                # Superset redundancy
                if pair in pairSet:
                    buffer.append(pair)
                    
#               # pairs which share their dominee
#               else: 
#                   for p in pairSet:
#                       if pair.split(' >> ')[-1] == p.split(' >> ')[-1]:
#                           buffer.append(pair)
                    
            pairSet = buffer[:]

        return pairSet
        
        
    def getPairsInRanking(self, ranking):
        pairs = []
        
        for c in range(len(ranking) - 1):
            i = c + 1
            
            while i < len(ranking):
                pairs.append('%s >> %s' %(ranking[c], ranking[i]))
                i += 1
        
        return pairs

# TODO: Move RowTab and ColTab to a file where only RCD/BCD/LFCD/etc use them.
class RowTab(Tableau):
    "alternate constructor for a tableau"
    def __init__(self, rows, constraints=None, input='', outputs=None):
        Tableau.__init__(self, [])
        self.input = input
        if constraints==None: constraints = [''] * len(rows[0])
        self.hierarchy = constraints
        if outputs==None: outputs = [''] * len(rows)
        self.outputs = outputs
        self.violations = rows
        self.column_vlns = transpose(self.violations)
        self.setColTuples()

        self.initialize(start_from='attributes')
class ColTab(RowTab):
    "alternate constructor for a tableau"
    def __init__(self, col_tuples):
        RowTab.__init__(self,
                        constraints=map(fst, col_tuples),
                        rows=transpose(map(snd, col_tuples)))
class Comparative(Tableau):
    """A comparative tableau.
    As it stands, Comparative cannot be evalled, because its winner
    is pre-specified, and there can be only one. So winners stays empty.

    (Comparative uses self.winner : str instead of self.winner : [str]
    but this may be the Wrong Thing)"""
    def __init__(self, tab):
        """Construct a comparative tableau from a standard one, which must be
        evalled at the time this is called."""
        Tableau.__init__(self, [])
        self.input = tab.input
        self.hierarchy = tab.hierarchy
        self.outputs = list(tab.outputs)
        self.winner = self.outputs.pop(0)
        self.violations = map(cur(map, flip(sub), tab.violations[0]),
                              tab.violations[1:])
        self.column_vlns = transpose(self.violations)
        self.setColTuples()
        self.initialize(start_from='attributes')
    def getComparativeTuples(self):
        return self.col_tuples
    def getAbsoluteTableau(self):
        def raise_by_lowest(violations):
            return transpose([[vln - min(col) for vln in col]
                              for col in transpose(violations)])
        rows = raise_by_lowest([[0] * len(self.hierarchy)] + self.violations)
        return RowTab(rows,
                      self.hierarchy,
                      self.input,
                      [self.winner] + self.outputs)
    def getLaTeXTableau(self):
        """Produce a version of the tableau appropriate for graphical
        display.
        Maybe the winner should appear after each candidate instead of with
        the input, as it does on the latex output."""
        g = [[self.input + " ~ " + self.winner] + self.hierarchy]
        if self.isEvaled and self.winners:
            for out,row,fatalViolation in zip(self.outputs,
                                              self.violations,
                                              self.fatalViolations):
                r = [out]
                for col,(violation,minV) in \
                        enumerate(zip(row, self.minViolations)):
                    if col==fatalViolation:
                        r.append(fatalViolationAsString(minV, violation))
                    else:
                        r.append(num2WL(violation))
                g.append(r)
            return g
        else:
            return g + [[o]+map(num2WL, row) \
                        for o,row in zip(self.outputs, self.violations)]
    def update(self, matrix):
        "update self.tableau based on input from the view"
        def sgn(n):
            if n > 0: return 1
            if n < 0: return -1
            else:     return 0
        def update_vln(old,new):
            "int*str->int -- only update if changed (retains information)"
            if sgn(old)==WL2num(new): return old
            else:                     return WL2num(new)
        self.input, self.winner = map(str.strip, matrix[0][0].split("~"))
        self.hierarchy = matrix[0][1:]
        self.outputs = [row[0] for row in matrix[1:]]
        self.violations = [map(update_vln, olds, news[1:])
                           for olds, news in zip(self.violations,matrix[1:])]
        self.column_vlns = transpose(self.violations)
        self.setColTuples()
        self.initialize(start_from='attributes')
def fatalViolationAsString(fatal, viol):
    if fatal < viol and fatal >= 0:
        return "*"*(fatal+1) + "!" + "*"*(viol-fatal-1)
    else:
        return "*"*viol
def star2num(s):
    return s.count('*')
def WL2num(s):
    if s=="W": return 1
    if s=="L": return -1
    else:      return 0
def num2WL(n):
    if n > 0: return "W"
    if n < 0: return "L"
    else:     return ''

########################################################################
        
if __name__ == '__main__':

#   m = [['tEt','Max', 'Dep','NoCoda'], 
#       ['tEt', '', '','*'], 
#       ['tE', '*','',''],
#       ['tEti', '', '*','']
#   ]
    
    
    m = [['tEt','Max', 'Dep','NoCoda','Max', 'Dep','NoCoda','Max','NoCoda'], 
        ['tEt', 0,0,1,0,0,0,0,0], 
        ['tE', 1,0,0,1,0,0,0,0],
        ['tEti', 0,1,0,0,1,0,0,0],
        ['tEt2', 0,0,1,0,0,1,0,0], 
        ['tE2', 1,0,0,1,0,0,0,0],
        ['tEti2', 0,1,0,0,1,0,0,0]]
        
    gmr = Tableau(m)

    gmr.factorialTypology()
    
    print 'done' #gmr.getFactorialTypologyAsString()
    
    #print len(gmr.rankings)
#   gmr.eval()
# 
#       
#   for w in gmr.winners:
#       print "le gagnant est " + gmr.tableau[w][0]
# #     print gmr.tableau
#   
#   print gmr.toLaTeX()
    
